题面

前言

非常神仙的动态规划

解题思路

动态鬼规划

分析

感觉这道题还是比较看技巧的，（是谁想出来的，太妙了呀！推出去打

用 $L[i][j]$ 表示在 $[i,j]$ 这个区间左侧（也就是 $i-1$ 的位置）放多少石子可以保证先手必败

同上，用 $R[i][j]$ 表示在 $[i,j]$ 这个区间右侧放多少石子可以保证先手必败

接下去，我们要证明一下 $L[i][j]$ 和 $R[i][j]$ 的唯一（存在）性

$L[i][j]$ 和 $R[i][j]$ 的唯一性

以 $L[i][j]$ 为例（$R[i][j]$ 同理），

1、若 $L[i][j]$ 不唯一，设其中两个值分别为 $L_1,L_2$ （$L_1 < L_2$），显然 $L_2$ 可以经过先手取一次变成 $L_1$ 的状态，与此时与先手必败矛盾，所以 $L[i][j]$ 唯一存在

2、若 $L[i][j]$ 不存在，也就是说在 $[i,j]$ 区间石子左侧无论放多少，先手都是必胜态，那么也就是说从右侧拿石子就会达到一个必败态，但是由于，左侧的石子数可以任意，那么就变成了$L[i][j]$ 不唯一的情况（除左侧一堆石子数是不一样外，其他都一样），这与我们在 1 中得出的结论矛盾，一次 $L[i][j]$ 必定存在

考虑 $L[i][j]$ 和 $R[i][j]$ 的初始化

边界即为：$i=j$ 时， $L[i][i]$ 与 $R[i][i]$ 的状态，这个时候就是个 $Nim$ 游戏，显然 $L[i][i]=R[i][i]=a[i]$ 即可

考虑 $L[i][j]$ 和 $R[i][j]$ 的转移

以 $L[i][j]$ 为例，分类讨论

0、显然 $L[i][j]$ 的转移与 $L[i][j-1]$ 以及 $R[i][j-1]$ 有关，与 $L[i+1][j]$ 以及 $R[i+1][j]$ 无关

那么，令 $x=a[j]$ （第 $j$ 堆石子数），$l=L[i][j-1]$，$r=R[i][j-1]$

1、当 $r=x$ 时，$L[i][j]=0$

此时 $[i,j]$ 已是先手必败态，因此 $L[i][j]=0$ 即可

2、当 $x<l$ 且 $x<r$ 时，$L[i][j]=x$

也就是说此时两侧的石子数一致，无论先手怎么取，后手只要模仿先手在另一侧取相同的数量，这样就能保证先手先取完，此时左侧或右侧肯定仍有一堆没有取完，此时可以等价认为当前状态是 先手从 $l$ 或 $r$ 的状态取一定数量的石子转移而来

3、当 $l<x<r$ 时，$L[i][j]=x+1$

若先手在左侧取，剩下石子数为 $rest$ ，

当 $rest=0$ 时，等价于 先手在 $r$ 的状态下，在右侧取了一定数量的石子转移而来

当 $rest<l$ 时，后手只要将右侧的石头取到和 $rest$ 相同的数目，即可转移到 2 的情况

当 $rest=l$ 时，后手将右侧取完就可以让先手达到必败态

当 $rest>l$ 时，后手只要将右侧石子取到 $rest-1$ 即可重新回到当前状态

若先手在右侧取，剩下石子数为 $rest$ ，

当 $rest=0$ 时，后手把左侧石子取到 $l$ 即可

当 $rest<l$ 时，同上，取左侧，可以转移到 2 的情况

当 $rest>=l$ 时，后手通过在左侧或右侧取，使 左侧石子数=右侧石子数+1 即可

4、当 $l>x>r$ 时，$L[i][j]=x-1$

这种情况与 3 一致，可以认为只是互换了一下左右两侧而已

5、当 $x>l$ 且 $x>r$ 时，$L[i][j]=x$

若先手在左侧取，剩下石子数为 $rest$，

当 $rest=0$ 时，后手将右侧石子取至 $r$ 即可

当 $l<rest$ 时，可转移至 2

当 $l=rest$ 时，右侧直接取完

当 $rest \in [l,r]$ 或 $rest\in[r,l]$ 时，可转移至 3 或 4

当 $l<rest$ 且 $r<rest$ 时，保持当前状态即可

判断

由于左侧和右侧是等价的，因此最后只需判断 $L[2][n]$ 是否等于 $a[1]$

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rLL rgt LL
#define inf 0x7f7f7f7f
#define N 1003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
int n,T,a[N],L[N][N],R[N][N];
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int main()
{
    int i,j,l,r,k,x;
    T=read();
    while(T--) {
        n=read();
        for(i=1;i<=n;i++) L[i][i]=R[i][i]=a[i]=read();//初始化
        for(k=2;k<n;k++) {//枚举区间长度
            for(i=1,j=i+k-1;j<=n;i++,j++) {//枚举左右端点
                x=a[j],l=L[i][j-1],r=R[i][j-1];
                if(x==r) L[i][j]=0;//情况1
                else if((x>l&&x>r)||(x<l&&x<r)) L[i][j]=x;//情况2、5
                else if(r<x&&x<l) L[i][j]=x-1;//情况4
                else L[i][j]=x+1;//情况3
                x=a[i],l=L[i+1][j],r=R[i+1][j];//同理可得
                if(x==l) R[i][j]=0;
                else if((x>l&&x>r)||(x<l&&x<r)) R[i][j]=x;
                else if(l<x&&x<r) R[i][j]=x-1;
                else R[i][j]=x+1;
            }
        }
        putchar(a[1]==L[2][n]?'0':'1'),putchar('\n');
    }
    return 0;
}

参考&鸣谢

@Jason_Yvan(Luogu) @yybyyb(Luogu)

devil.